package 极客算法训练营.chapter07;

import java.util.*;

public class 组合 {

    class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> ans = new ArrayList<>();
            if (k <= 0 || k > n) return ans;
            Deque<Integer> stack = new ArrayDeque<>();
            dfs(n, k, 1, stack, ans);
            return ans;
        }

        private void dfs(int n, int k, int begin, Deque<Integer> stack, List<List<Integer>> ans) {
            //terminator
            if (stack.size() == k) {
                ans.add(new ArrayList<>(stack));
                return;
            }

            for (int i = begin; i <= n - (k - stack.size()) + 1 ; i++) {
                //process
                stack.push(i);
                //drill down
                dfs(n, k, i + 1, stack, ans);
                //reverse state
                stack.pop();
            }
        }
    }
}
